#include <stdio.h>
void Swap(int *p1,int*p2)
{
	int tmp=*p1;
	*p1=*p2;
	*p2=tmp;
	
}
void Print(int*a,int n)
{
	for(int i=0;i<n;i++)
		{
			printf("%d ",a[i]);
		}
	printf("\n");
}

void Address(int *a,int head,int middle,int tail)//三目取中法
{
	if(a[head]>a[tail])
		{
			if(a[tail]>a[middle])
				{
					Swap(&a[tail],&a[head]);
				}
			else if(a[head]<a[middle])
				{
					return;
				}
			else
				{
					Swap(&a[middle],&a[head]);
				}
		}
	else
		{
			if(a[head]>a[middle])
				{
					return;
				}
			else if(a[tail]<a[middle])
				{
					Swap(&a[tail],&a[head]);
				}
			else
				{
					Swap(&a[middle],&a[head]);
				}
		}
}
//hoare
//int  KeyAddress(int *a,int began,int end)//置换的过程
//{
//	Address(a,began,began+end/2,end);
//	int key=began;
//	while(began<end)
//		{
//			while(began<end&&a[end]>=a[key])//遇到的数据可能是和key相等,还有可能右边一直都比key小或者大他们相遇不会停下来
//			{
//				end--;
//			}
//			while(began<end&&a[began]<=a[key])
//				{
//					began++;
//				}
//			Swap(&a[began],&a[end]);
//		}
//	Swap(&a[began],&a[key]);
//	return began;
//}
//挖坑法

//int  KeyAddress(int *a,int began,int end)
//{
//	// Address(a,began,began+end/2,end);
//	int tmp=a[began];
//	int left=began;//把自身当成一个坑位
//	int right=end;
//	while(left<right)
//		{
//			while(left<right&&tmp<a[right])
//				{
//					right--;
//				}
//			a[left]=a[right];//之间覆盖
//			while(left<right&&tmp>a[left])
//				{
//					left++;
//				}
//			a[right]=a[left];
//		}
//	Swap(&tmp,&a[left]);
//	return left;
//}

//左右指针or快慢指针法
int  KeyAddress(int *a,int began,int end)
{
	int key=a[began];
	int prev=began;
	int cur=prev+1;
	while(cur<=end)
		{
			if(a[cur]<key&&cur!=++prev)
				{
					Swap(&a[cur],&a[prev]);
				}
			++cur;
		}
	Swap(&a[prev],&a[began]);
	return prev;
}


//void QuickSort(int* a, int left,int right)//递归版
//{
//	if(left>=right)//代表已经没有元素需要交换
//	{
//		return ;
//	}
//	int key =KeyAddress(a,left,right);
//	
//	//[left,key-1]key[key+1,right]
//	QuickSort(a,left,key-1);//左边区间,
//	QuickSort(a,key+1,right);//右边区间
//}

//void QuickSort(int* a, int left, int right)//迭代版
//{
//	STK index;//栈
//	StackInit(&index);//初始化栈
//	
//	//先进后出
//	StackPush(&index,right);//尾
//	StackPush(&index,left);//首
//	while(!CheckEmpty(&index))
//		{
//			StackPrint(&index);
//			int began=StackTop(&index);
//			StackPrint(&index);
//			int end=StackTop(&index);
//			
//			int key =KeyAddress(a,began,end);
//			if(began==end&&end==right)
//				{
//					break;
//				}
//			
//			if(key+1<end||key-1>began)
//				{
//					
//					StackPush(&index,end);
//					StackPush(&index,key+1);
//					StackPush(&index,key-1);
//					StackPush(&index,began);
//				}
//			
//		}
//	StackDestroy(&index);//销毁链表
//}
	
	


	
int main(int argc, char *argv[]) 
{
	int arr[]={25,34,56,65,99,86,72,66};
	Print(arr,sizeof(arr)/sizeof(arr[0]));
	QuickSort(arr,0,sizeof(arr)/sizeof(arr[0])-1);	
	Print(arr,sizeof(arr)/sizeof(arr[0]));
}
	
	